home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Applications / Python 1.3.3 / stdwin / Tools / glob.c < prev    next >
Text File  |  1995-12-21  |  15KB  |  684 lines
  1. /*
  2.  * Copyright (c) 1989 Stichting Mathematisch Centrum, Amsterdam, Netherlands.
  3.  * Written by Guido van Rossum (guido@cwi.nl).
  4.  * NO WARRANTIES!
  5.  * Freely usable and copyable as long as this copyright message remains intact.
  6.  */
  7.  
  8. /*
  9.  * Function glob() as proposed in Posix 1003.2 B.6 (rev. 9).
  10.  * Matches *, ? and [] in pathnames like sh(1).
  11.  * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
  12.  * The interface is a superset of the one defined in Posix 1003.2 (draft 9).
  13.  * Optional extra services, controlled by flags not defined by Posix:
  14.  * - replace initial ~username by username's home dir (~ by $HOME);
  15.  * - replace initial $var(but not $var elsewhere) by value of getenv("var");
  16.  * - escaping convention: \ inhibits any special meaning the following
  17.  *   character might have (except \ at end of string is kept);
  18.  * - harmonica matching: /foo/** matches all files in the tree under /foo,
  19.  *   including /foo itself.
  20.  * If you don't want code for $ or ~ or ** expansion, simply remove the
  21.  * corresponding #defines from glob.h.
  22.  */
  23.  
  24. #include <ctype.h>
  25. #include <errno.h>
  26. #include <string.h>
  27. #include <sys/types.h>
  28. #include <dirent.h>
  29. #ifdef SYSV
  30. #define MAXPATHLEN 1024
  31. #else
  32. #include <sys/param.h> /* For MAXPATHLEN */
  33. #endif
  34. #include <sys/stat.h>
  35. #include <stdio.h>
  36. #include <assert.h>
  37. #include <glob.h>
  38.  
  39. extern struct passwd *getpwnam();
  40. extern char *malloc();
  41. extern char *realloc();
  42. extern char *getenv();
  43. extern int errno;
  44.  
  45. #ifndef NULL
  46. #define NULL 0
  47. #endif
  48.  
  49. #ifndef STATIC
  50. #define STATIC static
  51. #endif
  52.  
  53. typedef int bool_t;
  54. #define FALSE 0
  55. #define TRUE 1
  56.  
  57. #define TILDE '~'
  58. #define DOLLAR '$'
  59. #define UNDERSCORE '_'
  60. #define QUOTE '\\'
  61.  
  62. #define SEP '/'
  63. #define DOT '.'
  64.  
  65. #define STAR '*'
  66. #define QUESTION '?'
  67. #define LBRACKET '['
  68. #define RBRACKET ']'
  69. #define NOT '!'
  70. #define RANGE '-'
  71.  
  72. #define EOS '\0'
  73.  
  74. #define HOME "HOME"
  75.  
  76. #define MARK    0x80
  77. #define META(c) ((c)|MARK)
  78. #define M_ALL META('*')
  79. #define M_ONE META('?')
  80. #define M_SET META('[')
  81. #define M_NOT META('!')
  82. #define M_RNG META('-')
  83. #define M_END META(']')
  84. #define ISMETA(c) (((c)&MARK) != 0)
  85.  
  86.  
  87. #if GLOB_TILDE | GLOB_DOLLAR
  88.  
  89. /* Copy the characters between str and strend to buf, and append a
  90.    trailing zero.  Assumes buf is MAXPATHLEN+1 long.  Returns buf. */
  91.  
  92. STATIC char *
  93. makestr(buf, str, strend)
  94.     char *buf; /* Size MAXPATHLEN+1 */
  95.     char *str, *strend;
  96. {
  97.     int n;
  98.     
  99.     n = strend - str;
  100.     if (n > MAXPATHLEN)
  101.         n = MAXPATHLEN;
  102.     strncpy(buf, str, n);
  103.     buf[n] = EOS;
  104.     return buf;
  105. }
  106.  
  107. /* Append string to buffer, return new end of buffer.  Guarded. */
  108.  
  109. STATIC char *
  110. addstr(dest, src, end)
  111.     char *dest;
  112.     char *src;
  113.     char *end;
  114. {
  115.     while (*dest++ = *src++) {
  116.         if (dest >= end)
  117.             break;
  118.     }
  119.     return --dest;
  120. }
  121.  
  122. #endif /* GLOB_TILDE | GLOB_DOLLAR */
  123.  
  124.  
  125. #if GLOB_TILDE
  126.  
  127. #include <pwd.h>
  128.  
  129. /* Find a user's home directory, NULL if not found */
  130.  
  131. STATIC char *
  132. gethome(username)
  133.     char *username;
  134. {
  135.     struct passwd *p;
  136.     
  137.     p = getpwnam(username);
  138.     if (p == NULL)
  139.         return NULL;
  140.     else
  141.         return p->pw_dir;
  142. }
  143.  
  144. #endif /* GLOB_TILDE */
  145.  
  146.  
  147. /* String compare for qsort */
  148.  
  149. STATIC int
  150. compare(p, q)
  151.     char **p;
  152.     char **q;
  153. {
  154.     return strcmp(*p, *q);
  155. }
  156.  
  157.  
  158. /* The main glob() routine: does optional $ and ~ substitution,
  159.    compiles the pattern (optionally processing quotes),
  160.    calls glob1() to do the real pattern matching,
  161.    and finally sorts the list (unless unsorted operation is requested).
  162.    Returns 0 if things went well, nonzero if errors occurred.
  163.    It is not an error to find no matches. */
  164.  
  165. int
  166. glob(pattern, flags, errfunc, pglob)
  167.     char *pattern;
  168.     int flags;
  169.     int (*errfunc)();
  170.     glob_t *pglob;
  171. {
  172.     char *patnext = pattern;
  173.     char patbuf[MAXPATHLEN+1];
  174.     char *bufnext, *bufend;
  175.     char *compilebuf, *compilepat;
  176.     char *p, *q;
  177.     char c;
  178.     int err;
  179.     int oldpathc;
  180.     
  181.     if ((flags & GLOB_APPEND) == 0) {
  182.         pglob->gl_pathc = 0;
  183.         pglob->gl_pathv = NULL;
  184.         if ((flags & GLOB_DOOFFS) == 0)
  185.             pglob->gl_offs = 0;
  186.     }
  187.     pglob->gl_flags = flags;
  188.     pglob->gl_errfunc = errfunc;
  189.     oldpathc = pglob->gl_pathc;
  190.     
  191.     bufnext = patbuf;
  192.     bufend = bufnext+MAXPATHLEN;
  193.     
  194. #if GLOB_DOLLAR | GLOB_TILDE
  195.     c = *patnext;
  196. #endif
  197.     
  198. #if GLOB_DOLLAR
  199.     if (c == DOLLAR && (flags & GLOB_DOLLAR)) {
  200.         p = ++patnext;
  201.         while (isalnum(*p) || *p == UNDERSCORE)
  202.             ++p;
  203.         if ((q = getenv(makestr(bufnext, patnext, p))) != NULL)
  204.             bufnext = addstr(bufnext, q, bufend);
  205.         patnext = p;
  206.     }
  207. #endif /* GLOB_DOLLAR */
  208.  
  209. #if GLOB_TILDE
  210.     if (c == TILDE && (flags & GLOB_TILDE)) {
  211.         p = ++patnext;
  212.         while (*p != EOS && *p != SEP)
  213.             ++p;
  214.         if (p == patnext) {
  215.             q = getenv(HOME);
  216.             if (q == NULL)
  217.                 --patnext;
  218.             else
  219.                 bufnext = addstr(bufnext, q, bufend);
  220.         }
  221.         else {
  222.             q = gethome(makestr(bufnext, patnext, p));
  223.             if (q == NULL)
  224.                 --patnext;
  225.             else {
  226.                 bufnext = addstr(bufnext, q, bufend);
  227.                 patnext = p;
  228.             }
  229.         }
  230.     }
  231. #endif /* GLOB_DOLLAR */
  232.     
  233.     compilebuf = bufnext;
  234.     compilepat = patnext;
  235.     while (bufnext < bufend && (c = *patnext++) != EOS) {
  236.         switch (c) {
  237.         
  238.         case QUOTE:
  239.             if (!(flags & GLOB_QUOTE))
  240.                 *bufnext++ = QUOTE;
  241.             else {
  242.                 if ((c = *patnext++) == EOS) {
  243.                     c = QUOTE;
  244.                     --patnext;
  245.                 }
  246.                 *bufnext++ = c;
  247.             }
  248.             break;
  249.         
  250.         case STAR:
  251.             *bufnext++ = M_ALL;
  252.             break;
  253.         
  254.         case QUESTION:
  255.             *bufnext++ = M_ONE;
  256.             break;
  257.         
  258.         case LBRACKET:
  259.             c = *patnext;
  260.             if (c == NOT)
  261.                 ++patnext;
  262.             if (*patnext == EOS ||
  263.                     strchr(patnext+1, RBRACKET) == NULL) {
  264.                 *bufnext++ = LBRACKET;
  265.                 if (c == NOT)
  266.                     --patnext;
  267.                 break;
  268.             }
  269.             *bufnext++ = M_SET;
  270.             if (c == NOT)
  271.                 *bufnext++ = M_NOT;
  272.             c = *patnext++;
  273.             do {
  274.                 /* TO DO: quoting */
  275.                 *bufnext++ = c;
  276.                 if (*patnext == RANGE &&
  277.                         (c = patnext[1]) != RBRACKET) {
  278.                     *bufnext++ = M_RNG;
  279.                     *bufnext++ = c;
  280.                     patnext += 2;
  281.                 }
  282.             } while ((c = *patnext++) != RBRACKET);
  283.             *bufnext++ = M_END;
  284.             break;
  285.         
  286.         default:
  287.             *bufnext++ = c;
  288.             break;
  289.  
  290.         }
  291.     }
  292.     *bufnext = EOS;
  293.     
  294.     if ((err = glob1(patbuf, pglob)) != 0)
  295.         return err;
  296.     
  297.     if (pglob->gl_pathc == oldpathc) {
  298.         if (flags & GLOB_NOCHECK) {
  299.             if (!(flags & GLOB_QUOTE))
  300.                 strcpy(compilebuf, compilepat);
  301.             else {
  302.                 /* Copy pattern, interpreting quotes */
  303.                 /* This is slightly different than the
  304.                    interpretation of quotes above --
  305.                    which should prevail??? */
  306.                 while (*compilepat != EOS) {
  307.                     if (*compilepat == QUOTE) {
  308.                         if (*++compilepat == EOS)
  309.                             --compilepat;
  310.                     }
  311.                     *compilebuf++ = *compilepat++;
  312.                 }
  313.                 *compilebuf = EOS;
  314.             }
  315.             return globextend(patbuf, pglob);
  316.         }
  317.     }
  318.     else {
  319.         if (!(flags & GLOB_NOSORT))
  320.             qsort((char*)
  321.                 (pglob->gl_pathv + pglob->gl_offs + oldpathc),
  322.                 pglob->gl_pathc - oldpathc,
  323.                 sizeof(char*), compare);
  324.     }
  325.     
  326.     return 0;
  327. }
  328.  
  329. STATIC int
  330. glob1(pattern, pglob)
  331.     char *pattern;
  332.     glob_t *pglob;
  333. {
  334.     char pathbuf[MAXPATHLEN+1];
  335.     
  336.     /* A null pathname is invalid (Posix 1003.1 sec. 2.4 last sentence) */
  337.     if (*pattern == EOS)
  338.         return 0;
  339.     return glob2(pathbuf, pathbuf, pattern, pglob);
  340. }
  341.  
  342. /* Functions glob2 and glob3 are mutually recursive; there is one level
  343.    of recursion for each segment in the pattern that contains one or
  344.    more meta characters. */
  345.  
  346. STATIC int
  347. glob2(pathbuf, pathend, pattern, pglob)
  348.     char *pathbuf; /*[MAXPATHLEN+1]*/
  349.     char *pathend;
  350.     char *pattern;
  351.     glob_t *pglob;
  352. {
  353.     bool_t anymeta = FALSE;
  354.     char *p, *q;
  355.     
  356.     /* Loop over pattern segments until end of pattern or until
  357.        segment with meta character found. */
  358.     for (;;) {
  359.         /* End of pattern? */
  360.         if (*pattern == EOS) {
  361.             struct stat sbuf;
  362.             *pathend = EOS;
  363.             if (stat(pathbuf, &sbuf) != 0)
  364.                 return 0; /* Need error call here? */
  365.             if ((pglob->gl_flags & GLOB_MARK) &&
  366.                     pathend[-1] != SEP &&
  367.                     (sbuf.st_mode & S_IFMT) == S_IFDIR) {
  368.                 *pathend++ = SEP;
  369.                 *pathend = EOS;
  370.             }
  371.             return globextend(pathbuf, pglob);
  372.         }
  373.         
  374.         /* Find end of next segment, copy tentatively to pathend */
  375.         q = pathend;
  376.         p = pattern;
  377.         while (*p != EOS && *p != SEP) {
  378.             if (ISMETA(*p))
  379.                 anymeta = TRUE;
  380.             *q++ = *p++;
  381.         }
  382.         
  383.         if (!anymeta) {
  384.             /* No expansion needed, go on with next segment */
  385.             pathend = q;
  386.             pattern = p;
  387.             while (*pattern == SEP)
  388.                 *pathend++ = *pattern++;
  389.         }
  390.         else {
  391.             /* Need expansion, start another recursion level */
  392. #ifdef GLOB_HARMONICA
  393.             if ((pglob->gl_flags & GLOB_HARMONICA) &&
  394.                     isharmonica(pattern, p)) {
  395.                 /* Special case: foo|**|bar matches foo|bar */
  396.                 int err = glob2a(pathbuf, pathend, p, pglob);
  397.                 if (err != 0)
  398.                     return err;
  399.             }
  400. #endif /* GLOB_HARMONICA */
  401.             return glob3(pathbuf, pathend, pattern, p, pglob);
  402.         }
  403.     }
  404.     /* We never get here */
  405. }
  406.  
  407. #ifdef GLOB_HARMONICA
  408.  
  409. STATIC int
  410. glob2a(pathbuf, pathend, restpattern, pglob)
  411.     char *pathbuf; /*[MAXPATHLEN+1]*/
  412.     char *pathend;
  413.     char *restpattern;
  414.     glob_t *pglob;
  415. {
  416.     /* Various special cases to get foo|**|bar right.
  417.        Table (| substituted for / to avoid ending the comment!):
  418.     
  419.         pathbuf:    restpattern:
  420.                 ** (1)        **| (2)        **|bar (3)
  421.        (A)    foo/        foo        foo/        foo/bar
  422.        (B)    /        /        /        /bar
  423.        (C)    empty        none        none        bar
  424.     
  425.        In case (2), any number of tailing slashes might be present:
  426.        **|||||||.
  427.        
  428.        Note that, because of the way glob2() and glob3() work,
  429.        if pathbuf is not empty, it ends in a slash.
  430.        Similarly, we know that restpattern[0] is either a slash
  431.        or the end of the string.
  432.     */
  433.     
  434.     int err;
  435.     
  436.     if (pathend > pathbuf) { /* Cases (A) and (B) */
  437.         if (restpattern[0] == SEP) /* Cases (2) and (3) */
  438.             restpattern++;
  439.         else if (pathend >= pathbuf+2) /* Case (A)(1) */
  440.             pathend--; /* <--- Ouch! */
  441.         /* Else, case (B)(1), nothing changes */
  442.     }
  443.     else { /* Case (C) */
  444.         while (restpattern[0] == SEP)
  445.             restpattern++;
  446.         if (*restpattern == EOS) /* Cases (1) or (2) -- don't match */
  447.             return 0;
  448.     }
  449.     
  450.     err = glob2(pathbuf, pathend, restpattern, pglob);
  451.     *pathend = SEP; /* Restore slash removed by line 'Ouch!' above */
  452.     return err;
  453. }
  454.  
  455. #endif /* GLOB_HARMONICA */
  456.  
  457. STATIC int
  458. glob3(pathbuf, pathend, pattern, restpattern, pglob)
  459.     char *pathbuf; /*[MAXPATHLEN+1]*/
  460.     char *pathend;
  461.     char *pattern, *restpattern;
  462.     glob_t *pglob;
  463. {
  464.     DIR *dirp;
  465.     struct dirent *dp;
  466.     int len;
  467.     int err;
  468. #ifdef GLOB_HARMONICA
  469.     int harmonica = (pglob->gl_flags & GLOB_HARMONICA) &&
  470.                 isharmonica(pattern, restpattern);
  471. #endif /* GLOB_HARMONICA */
  472.     
  473.     *pathend = EOS;
  474.     errno = 0;
  475.     if ((dirp = opendir(*pathbuf ? pathbuf : ".")) == NULL) {
  476.         /* TO DO: don't call for ENOENT or ENOTDIR */
  477.         if (pglob->gl_errfunc != NULL &&
  478.                 (*pglob->gl_errfunc)(pathbuf, errno) != 0 ||
  479.                 (pglob->gl_flags & GLOB_ERR))
  480.             return GLOB_ABEND;
  481.         else
  482.             return 0;
  483.     }
  484.     
  485.     err = 0;
  486.     
  487.     /* Search directory for matching names */
  488.     while ((dp = readdir(dirp)) != NULL) {
  489.         if (dp->d_name[0] == DOT && *pattern != DOT)
  490.             continue; /* Initial DOT must be matched literally */
  491.         if (
  492. #ifdef GLOB_HARMONICA
  493.             !harmonica &&
  494. #endif
  495.             !match(dp->d_name, pattern, restpattern))
  496.             continue; /* No match */
  497.         len = strlen(dp->d_name);
  498.         strcpy(pathend, dp->d_name);
  499.         err = glob2(pathbuf, pathend+len, restpattern, pglob);
  500.         if (err != 0)
  501.             break;
  502. #ifdef GLOB_HARMONICA
  503.         if (harmonica) {
  504.             pathend[len] = EOS;
  505.             if (isdir(pathbuf)) {
  506.                 pathend[len++] = SEP;
  507.                 pathend[len] = EOS;
  508.                 err = glob3(pathbuf, pathend+len,
  509.                     pattern, restpattern, pglob);
  510.                 if (err != 0)
  511.                     break;
  512.             }
  513.         }
  514. #endif /* GLOB_HARMONICA */
  515.     }
  516.     /* TO DO: check error from readdir? */
  517.     
  518.     closedir(dirp);
  519.     return err;
  520. }
  521.  
  522.  
  523. #ifdef GLOB_HARMONICA
  524.  
  525. /* Test for harmonica pattern (a pattern consisting of exactly two stars) */
  526.  
  527. STATIC bool_t
  528. isharmonica(pat, patend)
  529.     char *pat, *patend;
  530. {
  531.     return (pat[0] & 0xff) == M_ALL && (pat[1] & 0xff) == M_ALL &&
  532.             pat+2 == patend;
  533. }
  534.  
  535. /* Test for directory -- use lstat() to avoid endless recursion */
  536.  
  537. STATIC bool_t
  538. isdir(path)
  539.     char *path;
  540. {
  541.     struct stat sbuf;
  542.     
  543.     if (lstat(path, &sbuf) < 0)
  544.         return FALSE;
  545.     return (sbuf.st_mode & S_IFMT) == S_IFDIR;
  546. }
  547.  
  548. #endif /* GLOB_HARMONICA */
  549.  
  550.  
  551. /* Extend the gl_pathv member of a glob_t structure to accomodate
  552.    a new item, add the new item, and update gl_pathc.
  553.    
  554.    *** This assumes the BSD realloc, which only copies the block
  555.    when its size crosses a power-of-two boundary; for v7 realloc,
  556.    this would cause quadratic behavior. ***
  557.    
  558.    Return 0 if new item added, error code if memory couldn't be allocated.
  559.    
  560.    Invariant of the glob_t structure:
  561.    
  562.     Either gl_pathc is zero and gl_pathv is NULL; or
  563.     gl_pathc > 0 and gl_pathv points to (gl_offs + gl_pathc + 1) items.
  564. */
  565.  
  566. STATIC int
  567. globextend(path, pglob)
  568.     char *path;
  569.     glob_t *pglob;
  570. {
  571.     register char **pathv;
  572.     register int i;
  573.     unsigned int newsize;
  574.     unsigned int copysize;
  575.     char *copy;
  576.     
  577.     newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
  578.     if ((pathv = pglob->gl_pathv) == NULL)
  579.         pathv = (char **)malloc(newsize);
  580.     else
  581.         pathv = (char **)realloc((char *)pathv, newsize);
  582.     if (pathv == NULL)
  583.         return GLOB_NOSPACE;
  584.     
  585.     if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
  586.         /* First time around -- clear initial gl_offs items */
  587.         pathv += pglob->gl_offs;
  588.         for (i = pglob->gl_offs; --i >= 0; )
  589.             *--pathv = NULL;
  590.     }
  591.     pglob->gl_pathv = pathv;
  592.     
  593.     copysize = strlen(path) + 1;
  594.     if ((copy = malloc(copysize)) != NULL) {
  595.         strcpy(copy, path);
  596.         pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
  597.     }
  598.     pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
  599.     
  600.     return (copy == NULL) ? GLOB_NOSPACE : 0;
  601. }
  602.  
  603.  
  604. /* Pattern matching function for filenames.
  605.    Each occurrence of the * pattern causes a recursion level. */
  606.  
  607. STATIC bool_t
  608. match(name, pat, patend)
  609.     register char *name;
  610.     register char *pat, *patend;
  611. {
  612.     char c;
  613.     
  614.     while (pat < patend) {
  615.         c = *pat++;
  616.         switch (c & 0xff) {
  617.  
  618.         case M_ONE:
  619.             if (*name++ == EOS)
  620.                 return FALSE;
  621.             break;
  622.  
  623.         case M_ALL:
  624.             if (pat == patend)
  625.                 return TRUE;
  626.             for (; *name != EOS; ++name) {
  627.                 if (match(name, pat, patend))
  628.                     return TRUE;
  629.             }
  630.             return FALSE;
  631.  
  632.         case M_SET:
  633.             {
  634.             char k;
  635.             bool_t ok;
  636.             bool_t negate_range;
  637.             
  638.             ok = FALSE;
  639.             k = *name++;
  640.             if (negate_range = (*pat & 0xff) == M_NOT)
  641.                 ++pat;
  642.             while (((c = *pat++) & 0xff) != M_END) {
  643.                 if ((*pat & 0xff) == M_RNG) {
  644.                     if (c <= k && k <= pat[1])
  645.                         ok = TRUE;
  646.                     pat += 2;
  647.                 }
  648.                 else if (c == k)
  649.                     ok = TRUE;
  650.             }
  651.             if (ok == negate_range)
  652.                 return FALSE;
  653.             break;
  654.             }
  655.  
  656.         default:
  657.             if (*name++ != c)
  658.                 return FALSE;
  659.             break;
  660.  
  661.         }
  662.     }
  663.     return *name == EOS;
  664. }
  665.  
  666.  
  667. /* Free allocated data belonging to a glob_t structure.
  668.    This is part of the Posix interface. */
  669.  
  670. void
  671. globfree(pglob)
  672.     glob_t *pglob;
  673. {
  674.     if (pglob->gl_pathv != NULL) {
  675.         char **pp = pglob->gl_pathv + pglob->gl_offs;
  676.         int i;
  677.         for (i = 0; i < pglob->gl_pathc; ++i) {
  678.             if (*pp != NULL)
  679.                 free(*pp);
  680.         }
  681.         free((char *)pp);
  682.     }
  683. }
  684.